package com.zjj.learn.algorithmPlus.segment2.binaryTree;

import java.util.LinkedList;
import java.util.List;

/**
 * @author zjj_admin
 */
public class BinaryTreeNonRecursionTraversal {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(new TreeNode(new TreeNode(9), 2, new TreeNode(6)),
                1,
                new TreeNode(null, 3, new TreeNode(5)));
        //前序遍历
        List<String> list = order(root);
        System.out.println("list = " + list);
        String preOrder = preOrder(root);
        System.out.println("preOrder = " + preOrder);

        String inOrder = inOrder(root);
        System.out.println("inOrder = " + inOrder);

        String postOrder = postOrder(root);
        System.out.println("postOrder = " + postOrder);
    }

    /**
     * 使用非递归的方式求解，在一个方法中实现
     * 实现前序遍历，中序遍历和后续遍历
     *
     * @param root
     */
    static List<String> order(TreeNode root) {
        TreeNode curr = root;
        StringBuilder pre = new StringBuilder("preOrder:");
        StringBuilder in = new StringBuilder("inOrder:");
        StringBuilder post = new StringBuilder("postOrder:");
        //定义一个栈，用于存储当前节点的父节点
        LinkedList<TreeNode> s = new LinkedList();
        TreeNode pop = null;
        while (curr != null || !s.isEmpty()) {
            if (curr != null) {
                s.push(curr);
                pre.append(curr.val + " ");
                //依次向左边遍历
                curr = curr.left;
            } else {
                TreeNode peek = s.peek();
                if (peek.right == null) {
                    in.append(peek.val + " ");
                    //当没有右节点时
                    pop = s.pop();
                    //这一行打印的是中序遍历的结果
                    post.append(pop.val + " ");
                } else if (peek.right == pop) {
                    //当右节点已经遍历结束时
                    pop = s.pop();
                    //这一行打印的是中序遍历的结果
                    post.append(pop.val + " ");
                } else {
                    //右节点不为空并且没有遍历
                    in.append(peek.val + " ");
                    curr = peek.right;
                }
            }
        }
        return List.of(pre.toString(), in.toString(), post.toString());
    }


    /**
     * 前序遍历
     * 使用非递归的方式
     *
     * @param root
     */
    static String preOrder(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList();
        StringBuilder res = new StringBuilder();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                res.append(curr.val).append(" ");
                stack.push(curr);
                curr = curr.left;
            } else {
                //弹栈
                TreeNode pop = stack.pop();
                curr = pop.right;
            }
        }
        return res.toString();
    }


    /**
     * 中序遍历
     * 使用非递归的方式
     *
     * @param root
     */
    static String inOrder(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList();
        StringBuilder res = new StringBuilder();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                //弹栈
                TreeNode pop = stack.pop();
                res.append(pop.val).append(" ");
                curr = pop.right;
            }
        }
        return res.toString();
    }


    /**
     * 后续遍历
     * 使用非递归的方式
     *
     * @param root
     */
    static String postOrder(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList();
        StringBuilder res = new StringBuilder();
        TreeNode curr = root;
        TreeNode pop = null;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null || peek.right == pop) {
                    //弹栈
                    pop = stack.pop();
                    res.append(pop.val).append(" ");
                } else {
                    curr = peek.right;
                }
            }
        }
        return res.toString();
    }

}
